package kyssion.leetcode.num1_50;

import java.util.*;

public class code30_串联所有单词的子串 {

    public static void main(String[] args) {
        List<Integer> list = new code30_串联所有单词的子串().findSubstring3("wordgoodgoodgoodbastbastbastgood", new String[]{
                "word", "good", "bast", "good"
        });

        for (Integer i : list) {
            System.out.print(i + " ");
        }
    }

    /**
     * 1. 一般思路,其实就是暴利,利用只有固定的长度这一个特性,指定一个位置然后不停的递归地带就可以知道所有有用的数据了
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        if (words.length == 0) {
            return list;
        }
        int LEN = words.length * words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        int wordLength = words[0].length();
        int allNum = words.length;
        int nowNum = 0;
        for (int a = 0; a <= s.length() - LEN; a++) {
            String item = s.substring(a, a + wordLength);
            if (map.containsKey(item) && map.get(item) >= 1) {
                map.put(item, map.get(item) - 1);
                nowNum++;
                if (canIn(s, a + wordLength, map, LEN, wordLength, nowNum, allNum)) {
                    list.add(a);
                }
                nowNum--;
                map.put(item, map.get(item) + 1);
            }
        }
        return list;
    }

    public boolean canIn(String s, int start, Map<String, Integer> map, int LEN, int wordLength, int nowNum, int allNUm) {
        if (nowNum == allNUm) {
            return true;
        }
        if (start + wordLength > s.length()) {
            return false;
        }
        boolean isTrue = false;
        String item = s.substring(start, start + wordLength);
        if (map.containsKey(item) && map.get(item) >= 1) {
            map.put(item, map.get(item) - 1);
            nowNum++;
            if (canIn(s, start + wordLength, map, LEN, wordLength, nowNum, allNUm)) {
                isTrue = true;
            }
            nowNum--;
            map.put(item, map.get(item) + 1);
            return isTrue;
        }
        return isTrue;
    }

    /**
     * 第一种思路的优化,关键点是优化出现数值不够这种情况下的问题,第99行注释哪里
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring2(String s, String[] words) {
        if (words.length == 0)
            return new ArrayList<>();
        int num = 0;
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> wordsCount = new HashMap<>();
        Map<String, Integer> usedWords = new HashMap<>();
        for (String w : words)
            wordsCount.put(w, wordsCount.getOrDefault(w, 0) + 1);
        int wlen = words[0].length();
        for (int i = 0; i < wlen; i++, num = 0, usedWords.clear()) {
            for (int j = i; j + wlen <= s.length(); j += wlen) {
                String sub = s.substring(j, j + wlen);
                if (wordsCount.containsKey(sub)) {
                    num++;
                    usedWords.put(sub, usedWords.getOrDefault(sub, 0) + 1);
                    //假如出现了不符合要求的数据,就手动的执行一下跳跃的逻辑,后跳跃一步,这个地方设计非常巧妙,通过只想后校验一位的操作,可以解决hash重用的问题
                    while (usedWords.get(sub) > wordsCount.get(sub)) {
                        String rem = s.substring(j - (num - 1) * wlen, j - (num - 2) * wlen);
                        usedWords.put(rem, usedWords.get(rem) - 1);
                        num--;
                    }
                } else {
                    num = 0;
                    usedWords.clear();
                }
                if (num == words.length) {
                    res.add(j - (num - 1) * wlen);
                }
            }
        }
        return res;
    }

    /**
     * 方法2的hashmap方式的进一步优化
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring3(String s, String[] words) {
        int N = s.length();
        List<Integer> indexes = new ArrayList<Integer>(s.length());
        if (words.length == 0) {
            return indexes;
        }
        int M = words[0].length();
        if (N < M * words.length) {
            return indexes;
        }
        int last = N - M + 1;

        Map<String, Integer> mapping = new HashMap<>(words.length);//记录这个字符的位置
        int[][] table = new int[2][words.length];//记录上面mapping这个位置值的数量
        int failures = 0, index = 0;
        for (int i = 0; i < words.length; ++i) {
            Integer mapped = mapping.get(words[i]);
            if (mapped == null) {
                ++failures;//总map数量
                mapping.put(words[i], index);
                mapped = index++;
            }
            ++table[0][mapped];
        }

        int[] smapping = new int[last];//生成string中数据和字符的对比关系,之后的所有操作就不需要使用字符串对比了
        for (int i = 0; i < last; ++i) {
            String section = s.substring(i, i + M);
            Integer mapped = mapping.get(section);
            if (mapped == null) {
                smapping[i] = -1;
            } else {
                smapping[i] = mapped;
            }
        }

        //fix the number of linear scans
        for (int i = 0; i < M; ++i) {
            //reset scan variables
            int currentFailures = failures; //number of current mismatches
            int left = i, right = i;
            Arrays.fill(table[1], 0);
            //here, simple solve the minimum-window-substring problem
            while (right < last) {
                //这一步校验了当前的字符串所有的位置能否满足
                while (currentFailures > 0 && right < last) {
                    int target = smapping[right];
                    if (target != -1 && ++table[1][target] == table[0][target]) {
                        --currentFailures;
                    }
                    right += M;
                }
                //这里其实充分的利用了条件了,通过条件我们知道如果一个字符串能满足这个需求,只要满足一个关系式就是完美符合条件的长度=word的长度*数量
                //完美符合的判断方法是通过第一个循环获得了到一个指定位置的匹配情况,然后通过第二循环,判断是否是满足上面的这个公式
                while (currentFailures == 0 && left < right) {
                    int target = smapping[left];
                    //这一块是算法最精妙的地方
                    //条件是这样的首先如果能进入这个函数,说明在right的位置的时候,已经满足的word中单词的匹配,但是不知道是不是超出的word中单词数量的限制
                    //1. 如果这个匹配的限制超出了总量的限制,直接进行下一个操作
                    //2. 如果这个没有超出限制,就表明这个串一定是在规定的范围中的
                    //3. 如果在规定的范围中总长度还超过了限制,就表明这个匹配失效(注意每次进行这部操作的时候只进行了最小长度的匹配,比如这样的串 abab 匹配 [a,b],将会运行两边算法)
                    if (target != -1 && --table[1][target] == table[0][target] - 1) {
                        int length = right - left;
                        //因为使用的是最小匹配,如果长度大于本应该匹配的长度说明不符合要求
                        if ((length / M) == words.length) {
                            indexes.add(left);
                        }
                        //这里其实和之前的第二种算法的逻辑相同,当满足条件,或者不满足条件的时候,向后移动一位继续查找是否满足
                        ++currentFailures;
                    }
                    left += M;//记录起点
                }
            }

        }
        return indexes;
    }

}
